/**
 * 前序遍历非递归
 */
// class TreeNode {
//    int val;
//    TreeNode left;
//    TreeNode right;
//    TreeNode() {}
//    TreeNode(int val) { this.val = val; }
//    TreeNode(int val, TreeNode left, TreeNode right) {
//        this.val = val;
//        this.left = left;
//        this.right = right;
//      }
//}
//
//
//class Solution {
//    //非递归
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        Stack<TreeNode> stack = null;
//    }
//}
//class Solution{
//    public int preIndex = ;
//    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
//        //没有了左树  或者 没有了右树
//        if(inbegin > inend) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[preIndex]);
//        //找到当前根节点 在中序遍历中的位置
//        int rootIndex = findInorderIndex(inorder, preorder[preIndex],inbegin,inend);
//        preIndex++;
//
//        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
//
//        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
//
//        return root;
//
//    }
//
//    private int findInorderIndex(int[] inorder,int val,int inbegin,int inend) {
//        for(int i = inbegin;i <= inend;i++) {
//            if(inorder[i] == val) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//
//        return buildTreeChild(preorder,inorder,0,inorder.length-1);
//
//    }
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution5 {
    public int preIndex = 0;
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
        //对于左树:left = left   right = mid - 1;
        //对于右树:left = mid + 1    right = right
        //当遍历到只剩下一个根节点时就结束
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode((char) preorder[preIndex]);
        //找到当前根节点 在中序遍历中的位置
        int rootIndex = findInorderIndex(inorder, preorder[preIndex],inbegin,inend);
        //因为是前序遍历，所以最前面的那个为根节点，当找到一个根节点时需要加加往后找
        preIndex++;
        //前序遍历是：跟左右
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);

        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;

    }

    private int findInorderIndex(int[] inorder,int val,int inbegin,int inend) {
        for(int i = inbegin;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);

    }
}


